package com.kobeliu.entity;

/**
 * LeetCode 167
 *
 * 给定一个已按照 非递减顺序排列  的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
 *
 * 函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。
 *
 * 你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
 *
 * 示例 1：
 * 输入：numbers = [2,7,11,15], target = 9
 * 输出：[1,2]
 * 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
 */

public class Demo_34_No167 {

    public static void main(String[] args) {
        int[] nums = {2,7,11,15};

        int[] ints = twoSum(nums, 9);
        for (int i = 0; i < ints.length; i++) {
            System.out.println(ints[i]);
        }

    }


    /**
     * 时间复杂度过于高 O(n*n)
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum1(int[] nums, int target) {

        int len = nums.length;
//        int L = 0;
//        int R = len-1;
        int[] help = new int[2];

        for(int i=0;i<len-1;i++){
            while (i>0 && nums[i]==nums[i-1]) i++;
            for(int j=i+1;j<len;j++){
                while(j<len && j>i+1 && nums[j]==nums[j-1]) j++;

                if(j<len){
                    if(nums[i]+nums[j]==target){
                        help[0] = i+1;
                        help[1] = j+1;
                        return help;
                    }
                }
            }
        }
        return help;
    }

    /**
     * 0(n)  打败100%
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum(int[] nums, int target) {

        int len = nums.length;
        int L = 0;
        int R = len-1;
        int[] help = new int[2];
        int sum = 0;

        while(L<R){
            while(L>0 && nums[L]==nums[L-1]) L++;
            while(R<len-1&& nums[R]==nums[R+1]) R--;
            sum = nums[L]+nums[R];
            if(sum>target){
                R--;
            }else
            if(sum<target){
                L++;
            }else{
                String s = "dds";
                StringBuffer sb =  new StringBuffer("sddsds");
                sb.replace(0,3,s);
                System.out.println(sb);
                help[0] = L+1;
                help[1] = R+1;
                return help;
            }
        }

        return help;



    }



}
